package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author: xiaomi
 * @date: 2021/3/6
 * @description: 503. 下一个更大元素 II
 * https://leetcode-cn.com/problems/next-greater-element-ii/
 * 循环数组降循环处理（不破坏题意的情况下）：
 * 1.拉直：拷贝两个数组，长度为 2n-1;
 * 2.使用 索引的取余
 */
public class B_503_下一个更大元素II {

    static B_503_下一个更大元素II action = new B_503_下一个更大元素II();

    public static void main(String[] args) {
        test1();
        test3();
        test4();
    }

    static void test1() {
        //[2,-1,2]
        int[] nums = new int[]{1, 2, 1};
        int[] res = action.nextGreaterElements(nums);
        System.out.println(Arrays.toString(res));
    }

    static void test2() {
        //
        int[] nums = new int[]{1, 2, 3, 2, 1};
        int[] res = action.nextGreaterElements(nums);
        System.out.println(Arrays.toString(res));
    }

    static void test3() {
        //[-1,-1,-1,-1,-1]
        int[] nums = new int[]{1, 1, 1, 1, 1};
        int[] res = action.nextGreaterElements(nums);
        System.out.println(Arrays.toString(res));
    }

    static void test4() {
        //[2, 3, 4, 5, 6, -1, 6, 5, 6, 2, 3, 4]
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 5, 4, 5, 1, 2, 3};
        int[] res = action.nextGreaterElements(nums);
        System.out.println(Arrays.toString(res));
    }


    /**
     * 发现了一个规律：第一个 -1 出现的地方，该值就是 max
     * 我的方案：
     * 1.首先当成普通数组处理：使用一个双端队列，单调顺序记录值，当出现相同的值时从队头移除；
     * --
     * 这个思路用双端队列的方式是有问题的！
     * 用栈可以快速的解
     *
     * @param nums
     * @return
     */
    public int[] nextGreaterElementsFail(int[] nums) {
        if (nums == null) {
            return null;
        }
        int len = nums.length;
        if (len == 0) {
            return new int[0];
        }
        LinkedList<Integer> deque = new LinkedList<>();
        LinkedList<Integer> supportDeque = new LinkedList<>();
        deque.addLast(nums[0]);
        supportDeque.addLast(nums[0]);
        for (int i = 1; i < len; i++) {
            if (nums[i] == deque.peekLast()) {
                deque.addLast(nums[i]);
            }
            if (nums[i] > deque.peekLast()) {
                //将相同的入栈
                deque.addLast(nums[i]);
                supportDeque.addLast(nums[i]);
            }

        }
        //记录 -1 的值
        int index = 0;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < nums[i]) {
                deque.removeFirst();
                if (!supportDeque.isEmpty()) {
                    supportDeque.removeFirst();
                }

            }
            if (deque.isEmpty()) {
                res[i] = -1;
                index = i;
                break;
            } else {
                //此时队列仍然有值，则该值就是 下一个更大的值
                if (deque.peekFirst() == nums[i]) {
                    deque.removeFirst();
                    if (supportDeque.peekFirst() == nums[i]) {
                        supportDeque.removeFirst();
                    }
                    //寻找下一个更大的值（但是由于队列不能使用索引，于是采用了新增队列进行辅助的方法）
                    if (supportDeque.isEmpty()) {
                        res[i] = -1;
                        index = i;
                        break;
                    }
                    res[i] = supportDeque.peekFirst();
                } else {
                    res[i] = deque.peekFirst();
                }
            }
        }
        //此时完成 max 之前的计算,并且队列必然为空
        if (index + 1 == len) {
            return res;
        }
        deque.addLast(nums[index + 1]);
        supportDeque.addLast(nums[index + 1]);
        for (int i = index + 2; i < len; i++) {
            if (nums[i] == deque.peekLast()) {
                deque.addLast(nums[i]);
            }
            if (nums[i] > deque.peekLast()) {
                //将相同的入栈
                deque.addLast(nums[i]);
                supportDeque.addLast(nums[i]);
            }
        }
        //从头再进行补充
        for (int i = 0; i <= index; i++) {
            if (nums[i] == deque.peekLast()) {
                deque.addLast(nums[i]);
            }
            if (nums[i] > deque.peekLast()) {
                //将相同的入栈
                deque.addLast(nums[i]);
                supportDeque.addLast(nums[i]);
            }
        }
        //再将剩余的处理掉即可
        for (int i = index + 1; i < len; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < nums[i]) {
                deque.removeFirst();
                if (!supportDeque.isEmpty()) {
                    supportDeque.removeFirst();
                }
            }
            if (deque.isEmpty()) {
                res[i] = -1;
            } else {
                //此时队列仍然有值，则该值就是 下一个更大的值
                if (deque.peekFirst() == nums[i]) {
                    deque.removeFirst();
                    if (!supportDeque.isEmpty()) {
                        if (supportDeque.peekFirst() == nums[i]) {
                            supportDeque.removeFirst();
                        }
                    }
                    //寻找下一个更大的值（但是由于队列不能使用索引，于是采用了新增队列进行辅助的方法）
                    if (supportDeque.isEmpty()) {
                        res[i] = -1;
                    } else {
                        res[i] = supportDeque.peekFirst();
                    }
                } else {
                    res[i] = deque.peekFirst();
                }
            }
        }
        return res;
    }

    public int[] nextGreaterElements(int[] nums) {
        if (nums == null) {
            return null;
        }
        int len = nums.length;
        if (len == 0) {
            return new int[0];
        }
        ArrayDeque<Integer> valueDeque = new ArrayDeque<>(len);
        valueDeque.addLast(nums[0]);
        ArrayDeque<Integer> indexDeque = new ArrayDeque<>(len);
        indexDeque.addLast(0);
        //结果
        int[] res = new int[len];
        for (int i = 1; i < len; i++) {
            if (nums[i] <= valueDeque.peekLast()) {

            } else {
                while (!valueDeque.isEmpty() && valueDeque.peekLast() < nums[i]) {
                    valueDeque.removeLast();
                    Integer lastIndex = indexDeque.removeLast();
                    res[lastIndex] = nums[i];
                }
            }
            valueDeque.addLast(nums[i]);
            indexDeque.addLast(i);
        }
        //此时已经完成第一遍
        //此时 index 为 max 的索引
        Integer index = indexDeque.removeFirst();
        valueDeque.removeFirst();
        res[index] = -1;
        if (indexDeque.isEmpty()) {
            //如果已经为空-> 计算完毕
            return res;
        }
        //完成从 开始到 index 的补充
        for (int i = 0; i <= index; i++) {
            while (!valueDeque.isEmpty() && valueDeque.peekLast() < nums[i]) {
                valueDeque.removeLast();
                Integer lastIndex = indexDeque.removeLast();
                res[lastIndex] = nums[i];
            }
        }
        //如果此时依然还有值，都设置为 -1
        while (!indexDeque.isEmpty()){
            res[indexDeque.removeLast()] = -1;
        }
        return res;
    }
}
